#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution
{
public:
  // leetcode84柱状图中的最大矩形：维持一个单调递增栈
  int largestRectangleArea(vector<int> heights)
  {
    unsigned long size = heights.size();

    if (size == 1)
    {
      return heights[0];
    }

    heights.insert(heights.begin(), 0);
    heights.push_back(0);

    int res = 0;
    stack<int> stk;
    stk.push(0);

    // 遍历柱子
    int res = 0;
    for (int i = 1; i < size; ++i)
    {

      while (!stk.empty() && heights[i] < heights[stk.top()])
      {
        // 出栈
        int hight = heights[stk.top()];
        stk.pop();

        int width = i - stk.top() - 1;
        res = max(res, hight * width);
      }
      stk.push(i);
    }
    return res;
  }

  // leetcode.42接雨水：维持一个单调递减栈
  int trap(vector<int> &heights)
  {
    int res = 0;
    stack<int> st; // 没有左右哨兵的增加，和最大矩形面积不一样
    for (int i = 0; i < heights.size(); i++)
    {
      while (!st.empty() && heights[i] > heights[st.top()])
      {
        int height1 = heights[st.top()];
        st.pop();

        if (st.empty)
        {
          break;
        }
        int height = min(heights[st.top()], heights[i]) - height1;
        int width = i - st.top() - 1;
        res += height * width;
      }
      st.push(i);
    }
    return res;
  }

  // leetcode85:二维矩阵中的最大矩形
  //本质上是对矩阵中的每行，均依次执行84题算法
  //每一层看作是柱状图，可以套用84题柱状图的最大面积
  int maximalRectangle(vector<vector<char>> &matrix)
  {
    if (0 == matrix.size())
      return 0;
    int rows = matrix.size(), cols = matrix[0].size();
    vector<int> heights(cols, 0); // 每一行就是一个高度为1的直方图
    int res = 0;
    // 每一行看成一个直方图
    for (int i = 0; i < rows; i++)
    {
      for (int j = 0; j < cols; j++)
      {
        if ('1' == matrix[i][j])
        //字符匹配兄弟
        {
          heights[j] += matrix[i][j] - '0'; // 注意是加=， 每一行累加的
        }
        else
        {
          heights[j] = 0; // 只要某一行某列为0，这行这列之上积累的所有为1的都不作数了
        }
      }
      // 每一行调用一次最大柱状图面积
      res = max(res, largestRectangleArea(heights)); // 记住实现时，不能对heights传引用，因为加了讲个哨兵
    }
    return res;
  }

  // leetcode739.每日温度
  vector<int> dailyTemperatures(vector<int> &T)
  {
    int size = T.size();
    vector<int> res(size);
    if (size <= 1)
      return res;

    // 开始处理
    stack<int> stk; // 维持一个单调递减栈
    // 遍历温度列表
    for (int i = 0; i < size; i++)
    {
      while (!stk.empty() && T[i] > T[stk.top()])
      {
        int wait = i - stk.top();
        res[stk.top()] = wait;
        stk.pop();
      }
      stk.push(i);
    }

    return res;
  }
};

int main()
{
}